package algorithm.leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * @program: util
 * @description: 两个有序链表合成一个
 * @author: zhouliangliang
 * @create: 2021-04-06 16:38
 **/
public class TwoListToOne {

    public void merge(Integer[] array1, Integer[] array2) {
        Arrays.sort(array1);
        Arrays.sort(array2);

        System.out.println(array1.length + array2.length);

        int []newArray = new int[array1.length+array2.length];
        int index = array1.length > array2.length ? array2.length : array1.length;

        int i=0;
        int j=0;
        int k=0;
        while (i<index && j<index) {
            if(array1[i] < array2[j]) {
                newArray[k++] = array1[i++];
            }
            if(array1[i] > array2[j]) {
                newArray[k++] = array2[j++];
            }
            if(array1[i] == array2[j]) {
                newArray[k++] = array1[i++];
                newArray[k++] = array2[j++];
            }
        }

        if(i == array1.length) {
            for (; j < array2.length; j++) {
                newArray[k++] = array2[j];
            }
        }

        if(j == array2.length) {
            for (; i < array1.length; i++) {
                newArray[k++] = array1[i];
            }
        }

        System.out.println(newArray.length);

        Arrays.stream(newArray).forEach(item->{
            System.out.print(item + ",");
        });
    }

    public void mergeTwo(List<Integer> list1, CopyOnWriteArrayList<Integer> list2) {
        Collections.sort(list1);
        Collections.sort(list2);

        for(int i=0; i<list1.size(); i++) {
            int num = list1.get(i);
            addNumToList(num, list2);
        }
        System.out.println(list2);
    }

    public void addNumToList(Integer num, CopyOnWriteArrayList<Integer> list2) {
        boolean flag = false;
        for(int j=0; j< list2.size(); j++) {
            if(list2.get(j) > num) {
                list2.add(j-1, num);
                flag = true;
                break;
            }
        }

        if(!flag) {
            list2.add(num);
        }
    }

    public static void main(String[] args) {
        Integer []array1 = new Integer[]{1,5,3,6,2,8,4};
        Integer []array2 = new Integer[]{3,9,1,4,7,2,8,0,18,11,15,16,3};

//        new TwoListToOne().merge(array1,array2);
        CopyOnWriteArrayList list = new CopyOnWriteArrayList();
        list.addAll(Arrays.asList(array2));
        new TwoListToOne().mergeTwo(Arrays.asList(array1), list);
    }
}
